/*
 * @lc app=leetcode.cn id=987 lang=typescript
 *
 * [987] 二叉树的垂序遍历
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function verticalTraversal(root: TreeNode | null): number[][] {
  const inOrder = (node: TreeNode | null, row = 0, col = 0) => {
    if (node === null) return;
    inOrder(node.left, row + 1, col - 1);
    preOrderArray.push([node, row, col]);
    inOrder(node.right, row + 1, col + 1);
  };
  // 中序遍历，计算出所有节点的[row,col]
  const preOrderArray: [TreeNode, number, number][] = [];
  inOrder(root);
  // 按照col,row,value顺序排序
  preOrderArray.sort((a: [TreeNode, number, number], b: [TreeNode, number, number]): number => {
    if (a[2] === b[2]) {
      if (a[1] === b[1]) {
        return a[0].val - b[0].val;
      } else {
        return a[1] - b[1];
      }
    } else {
      return a[2] - b[2];
    }
  });
  // 将排序结果分组
  const hash: Map<number, number[]> = new Map();
  for (let i = 0; i < preOrderArray.length; i++) {
    const k = preOrderArray[i][2];
    const v = preOrderArray[i][0].val;
    if (hash.has(k)) {
      hash.get(k).push(v);
    } else {
      hash.set(k, [v]);
    }
  }
  return [...hash.values()];
}
// @lc code=end
